6 June 2018, Algebra|Coalgebra Seminar, Jouke Witteveen

Classically, complexity theory focuses on the hardest instances of a given length. A set is in P if there is a decision procedure for it that runs in polynomial time even on the most difficult-to-decide instances. Parameterized complexity theory, on the other hand, looks at the identification of easy instances. In this talk, we shall define parameterizations as independent objects and show that the class of parameterizations naturally forms a lattice. The parameterizations that put a given set in any of the standard parameterized complexity classes are filters in this lattice. From these insights, we conjecture a separation property for P.